The invention relates to a method and apparatus for segmenting data associated with an image into windows, classifying the image data within each window, and processing the data using a rendering algorithm during a single pass through the image data. It finds particular application in conjunction with the use of a spatial adaptive fuzzy rendering algorithm for blended rendering and will be described with particular reference thereto. However, it is to be appreciated that the present invention is also amenable to other like applications.
Data associated with an image is often stored in the form of multiple scanlines, each scanline comprising multiple pixels. When processing this type of image data, it is helpful to know the type of image represented by the data. For instance, the image data could represent text, graphics, pictures, a particular frequency halftone, a contone, or some other recognized image type. The image data could be all one type, or some combination of image types. Classifying image data into recognized image types is known as image segmentation.
Windowing is an important step to improve the accuracy and the robustness of an image segmentation algorithm. It is known in the art to take a page of image data and to separate the image data into windows of similar image types. However, windowing and rendering techniques usually require multiple passes through the image data. A first pass to generate and classify windows in the image data and a second pass to process and render the image data according to the image type classes.
For example, a page of image data may include a halftone picture with accompanying text describing the picture. In order to efficiently process the image data, it is known to separate the page of image data into two windows, a first window representing the halftone image, and a second window representing the text. Processing the page of image data is then efficiently carried out by tailoring the processing to the type of image data being processed.
It is also known to separate image data into windows and to classify and process the image data within the windows by making either one or two passes through the page of image data. Typically, the one-pass method uses local image statistics (e.g., image data for a central pixel and neighboring pixels or pixels in the same scanline). If local statistics are used, different parts of the same window may be classified differently, and undesirable artifacts may be generated when the rendering algorithm is suddenly switched from one to another. The one-pass method is quicker, but it does not allow the use of future context to correct for windows that have already been generated and classified incorrectly. Since local statistics (i.e., micro-segmentation) are usually not reliable and accurate enough to be used directly, two-pass windowing techniques are usually applied to improve both the accuracy and the robustness of image processing.
In the two-pass method, information obtained from all scanlines can be used to generate windows and classify the image type of the window. In other words, future context can be used when generating and classifying windows in the first and second scanlines. In the two-pass method, during the first pass, the image is separated into windows, and a judgment is made about the type of image data in each window. At the end of the first pass, the image type class for each pixel is recorded in memory. During the second pass, the information from the first pass (i.e., the image type class data) is used to process the image data. Unfortunately, storing image type information for each pixel of a page of image data requires a great deal of memory, which increases the cost of an apparatus performing this method.
U.S. Pat. No. 5,850,474 to Fan et al. discloses an example of a two-pass method and apparatus for segmenting image data into windows and for classifying the windows as typical image types. The method includes a step of making a first pass through the image data to identify windows and to record the beginning points and image types of each of the windows, and a step of making a second pass through the image data to label each of the pixels as a particular image type and to render each pixel accordingly.
Multiple accesses of image data are required in the two-pass method because windows can have different sizes, shapes and layout. To generate windows “correctly,” the entire page is first gone through. For example, two windows that are separated at the top of the page could merge at the bottom and become one. If only local statistics are used to classify the window before the entire page is examined, different regions of the same window can be classified in different classes. Therefore, different rendering algorithms are applied within the same window, and undesirable artifacts may be generated along the boundaries where the rendering algorithms are changed within the window. For example, a “V”-shape window 1 is shown in FIG. 1. If the left portion 3 is classified as a first image type class and rendered using a first rendering algorithm, and the right portion 5 is classified as a second image type class and rendered using a second rendering algorithm, at the area where the two parts are connected (i.e., boundaries 7, 9) undesirable artifacts may be observed due to the abrupt transition between the rendering algorithms. Previously, the solution has been to implement a two-pass method to go through the whole page to generate windows, store image data for the entire page, and render the image in a second pass. However, there are disadvantages in current two-pass windowing techniques. One disadvantage is that the image data needs to be accessed more than one time, causing delays. Another disadvantage is that a large memory area is required to store the image data before it can be output to storage or rendering devices. In many practical applications, the amount of memory required may prohibit the use of windowing techniques.